/*
 * Montgomery.js
 * Random number generator
 * Copyright (C) Jorge H. C. Lucema.
 */

/*global BigInteger */

var Montgomery = (function () {

//    "use strict";
    /**
     * Constructor
     * @param {BigInteger} m
     * @returns {Montgomery_L9.Montgomery}
     */
    var Montgomery = function (m) {
        this.m = m;
        this.mp = m.invDigit();
        this.mpl = this.mp & 0x7fff;
        this.mph = this.mp >> 15;
        this.um = 8191;
        this.mt2 = 2 * m.t;
    };

    Montgomery.montConvert = function (x) {
        var r = new BigInteger();
        x.abs().dlShiftTo(this.m.t, r);
        r.divRemTo(this.m, null, r);
        if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) {
            this.m.subTo(r, r);
        }
        return r;
    };

    Montgomery.montSqrTo = function (x, r) {
        x.squareTo(r);
        this.reduce(r);
    };

    Montgomery.montReduce = function (x) {
        var i, j, u0;
        while (x.t <= this.mt2) {
            x[x.t++] = 0; // pad x so am has enough room later
        }
        for (i = 0; i < this.m.t; ++i) {
            // faster way of calculating u0 = x[i]*mp mod (1<<dbits)
            j = x[i] & 0x7fff;
            u0 = (j * this.mpl + (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15)) & x.DM;
            // use am to combine the multiply-shift-add into one call
            j = i + this.m.t;
            x[j] += this.m.am(0, u0, x, i, 0, this.m.t);
            // propagate carry
            while (x[j] >= x.DV) {
                x[j] -= x.DV;
                x[++j]++;
            }
        }
        x.clamp();
        x.drShiftTo(this.m.t, x);
        if (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    };

    Montgomery.montMulTo = function (x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    };

    Montgomery.montRevert = function (x) {
        var r = new BigInteger();
        x.copyTo(r);
        this.reduce(r);
        return r;
    };

    Montgomery.prototype.convert = Montgomery.montConvert;
    Montgomery.prototype.sqrTo = Montgomery.montSqrTo;
    Montgomery.prototype.reduce = Montgomery.montReduce;
    Montgomery.prototype.mulTo = Montgomery.montMulTo;
    Montgomery.prototype.revert = Montgomery.montRevert;

    return Montgomery;
}());